package main.leetcode.clockin.May;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84.柱状图中最大的矩形
 *
 * <p>给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * <p>求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class day30 {
    public static void main(String[] args) {
        System.out.println(new day30().largestRectangleArea(new int[] {2, 1, 5, 6, 2, 3}));
        System.out.println(new day30().largestRectangleArea(new int[] {1, 1}));
        System.out.println(new day30().largestRectangleArea(new int[] {0, 9}));
    }

    // 暴力，永远滴美学
    //    public int largestRectangleArea(int[] heights) {
    //        if (heights == null || heights.length == 0) {
    //            return 0;
    //        }
    //        int n = heights.length;
    //        int res = 0;
    //        int tmp, min;
    //        for (int i = 0; i < n; ++i) {
    //            tmp = heights[i];
    //            min = tmp;
    //            for (int j = i + 1; j < n; ++j) {
    //                if (heights[j] >= min) {
    //                    tmp += min;
    //                } else {
    //                    res = Math.max(res, tmp);
    //                    min = heights[j];
    //                    tmp = (j - i + 1) * min;
    //                }
    //            }
    //            res = Math.max(res, tmp);
    //        }
    //        return res;
    //    }

    // 单调栈
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] newHeights = new int[n + 2];
        System.arraycopy(heights, 0, newHeights, 1, n);
        stack.addLast(0);
        int res = 0, curHeight, curWidth;
        for (int i = 0; i < n + 2; ++i) {
            while (newHeights[i] < newHeights[stack.peekLast()]) {
                curHeight = newHeights[stack.pollLast()];
                curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;
    }
}
